//
// Created by lxinp on 2022/8/30.
//

#ifndef DATASTRUCTURE_SIMPLE_HASHTABLE_H
#define DATASTRUCTURE_SIMPLE_HASHTABLE_H

#include <iostream>
#include <vector>

using namespace std;

namespace Simple {

/**
 * A simplified implementation of hash table using separate chaining
 * @tparam K
 * @tparam V
 * @tparam HashFn
 */
template<typename K, typename V, typename HashFn>
class HashTable {
private:
    struct Node {
        K key;
        V val;
        Node* next;
        Node() : key(0), val(0), next(nullptr) {}
        Node(K _key, V _val) : key(_key), val(_val), next(nullptr) {}
    };

public:
    explicit HashTable(int _capacity);
    ~HashTable();
    void insert(K key, V val);
    void remove(K& key);
    V& find(const K& key) const;
    V& operator[](const K& key);
    void print() const;

private:
    int size, capacity;
    HashFn hash;
    Node** table;
    V null_value;

    Node* find_node(const K& key) const;
};


class HashFn {
public:
    int operator()(const int& key) {
        return (97 * key + 171) % 31;
    }
};


/* Implementation starts from here */
template<typename K, typename V, typename HashFn>
HashTable<K, V, HashFn>::HashTable(int _capacity) : size(0), capacity(_capacity) {
    table = new Node*[_capacity];
    for (int i=0; i<capacity; i++) table[i] = nullptr;
    null_value = V(0);
}


template<typename K, typename V, typename HashFn>
HashTable<K, V, HashFn>::~HashTable() {
    for (int i=0; i<capacity; i++) {
        Node* node = table[i];
        while (node) {
            Node* temp = node;
            node = node->next;
            delete temp;
        }
    }
    delete table;
}


template<typename K, typename V, typename HashFn>
void HashTable<K, V, HashFn>::insert(K key, V val) {
    int index = hash(key) % capacity;
    Node* node = new Node(key, val);
    Node* place = table[index];
    if (!place) {
        table[index] = node;
    } else {
        node->next = place->next;
        table[index]->next = node;
    }
}


template<typename K, typename V, typename HashFn>
void HashTable<K, V, HashFn>::remove(K& key) {
    Node* node = find_node(key);
    if (!node) return;

    // Find the previous node on the same chain
    int index = hash(key) % capacity;
    Node* place = table[index];
    Node* dummy, * prev = dummy;
    dummy->next = place;
    while (prev->next->key != node->key) prev = prev->next;

    // Delete node
    Node* temp = prev->next;
    prev->next = node->next;
    delete temp;
}


template<typename K, typename V, typename HashFn>
V& HashTable<K, V, HashFn>::find(const K& key) const {
    Node* node = find_node(key);
    if (node) return node->val;
    return null_value;
}


template<typename K, typename V, typename HashFn>
V& HashTable<K, V, HashFn>::operator[](const K& key) {
    V& val = find(key);
    if (val) return val;
    insert(key, null_value);
    return find(key);
}


template<typename K, typename V, typename HashFn>
void HashTable<K, V, HashFn>::print() const {
    for (int i=0; i<capacity; i++) {
        Node* node = table[i];
        std::cout << "Key: " << node->key << "; Value: ";
        while (node) {
            std::cout << node->val;
            if (node->next) std::cout << ", ";
            node = node->next;
        }
        std::cout << std::endl;
    }
}


template<typename K, typename V, typename HashFn>
typename HashTable<K, V, HashFn>::Node* HashTable<K, V, HashFn>::find_node(const K& key) const {
    int index = hash(key) % capacity;
    if (!table[index]) return nullptr;
    Node* node = table[index];
    while (node) {
        if (node->key == key) return node;
        node = node->next;
    }
    return nullptr;
}
}


#endif //DATASTRUCTURE_SIMPLE_HASHTABLE_H
